/*
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

给定一棵树的前序遍历 preorder 与中序遍历  inorder。

请构造二叉树并返回其根节点。


构建一个二叉树需要构建三部分：root、左子树、右子树
左子树、右子树的构建，又包括：root、左子树、右子树
解题关键在于定位出根节点，划分出左右子树，然后 递归 构建左右子树

作者：xiao_ben_zhu
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/ding-wei-chu-gen-jie-dian-de-wei-zhi-hua-fen-zuo-y/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
* */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  return buildNode(preorder, inorder);
}

//根据前序遍历 和 中序遍历生成二叉树
var buildNode = function (preorder, inorder) {
  if (!preorder.length) return null/*空节点 要求返回null*/;

  let root = new TreeNode(preorder[0]); //根节点

  //在中序遍历中去找根节点的位置
  /*let p = 0;
  while (inorder[p] !== preorder[0]) {
    p++;
  }*/
  //
  const p = inorder.indexOf(preorder[0]);

  //根节点的左子树的中序遍历结果
  let leftIn = inorder.slice(0, p);
  //根节点的右子树的中序遍历结果
  let rightIn = inorder.slice(p + 1);

  //
  let leftPre = preorder.slice(1, p + 1);
  //
  let rightPre = preorder.slice(p + 1);

  root.left = buildNode(leftPre, leftIn);
  root.right = buildNode(rightPre, rightIn);

  return root;
};


function TreeNode(val, left, right) {
  this.val = (val === undefined ? 0 : val)
  this.left = (left === undefined ? null : left)
  this.right = (right === undefined ? null : right)
}
